Java 集合类学习 Map 集合

Map 集合接口

Map 集合的特点：存储一对数据（Key-Value），无序、无下标，键不可重复，值可重复

不要把 Map 和 HashMap搞混了，Map 单纯是一种 Key-Value 形式的存储方式，HashMap 只是它最常用的实现类

Map 接口中的常用方法

void clear()：删除该 Map 对象中所有键值对；
boolean containsKey(Object key)：查询 Map 中是否包含指定的 key 值；
boolean containsValue(Object value)：查询 Map 中是否包含一个或多个 value;
Set entrySet()：返回 map 中包含的键值对所组成的 Set 集合，每个集合都是 Map.Entry 对象。
Object get()：返回指定key对应的value，如果不包含key则返回null；
boolean isEmpty()：查询该Map是否为空；
Set keySet()：返回Map中所有key组成的集合；
Collection values()：返回该Map里所有value组成的Collection。
Object put(Object key,Object value)：添加一个键值对，如果集合中的key重复，则覆盖原来的键值对；
void putAll(Map m)：将Map中的键值对复制到本Map中；
Object remove(Object key)：删除指定的key对应的键值对，并返回被删除键值对的value，如果不存在，则返回null；
boolean remove(Object key,Object value)：删除指定键值对，删除成功返回true；
int size()：返回该Map里的键值对个数；

HashMap

最常用的Map，HashMap 的值是没有顺序的，他是按照 key 的 HashCode 来实现的，就是根据 key 的 HashCode 值来存储数据，根据 key 可以直接获取它的 Value，同时它具有很快的访问速度。

HashMap 最多只允许一条记录的 key 值为 Null（多条会覆盖），但是允许多条记录的 Value 为 Null。

使用位桶和链表实现（jdk1.8 改用红黑树存储而非链表），它是线程不安全的 Map，方法上都没有 synchronize 关键字修饰

Hashtable

与 HashMap 类似，不同的是 key 和 value 的值均不允许为 null；

Hashtable 是线程安全的一个 Map 实现类，它实现线程安全的方法是在各个方法上添加了 synchronize 关键字，即任一时刻只有一个线程能写 Hashtable，因此也导致了 Hashtale 在写入时会比较慢，且只有 Hashtable 是继承自 Dictionary，HashMap 和 TreeMap 都继承自 AbstractMap 抽象类，LinkedHashMap 继承自 HashMap。

但是现在已经不再推荐使用 HashTable 了，因为现在有了 ConcurrentHashMap 这个专门用于多线程场景下的 Map 实现类，其大大优化了多线程下的性能。

LinkedHashMap

LinkedHashMap 它的特点主要在于 Linked，带有这个字眼的就表示底层用的是链表来进行的存储。相对于其他的无序的 Map 实现类，还有像 TreeMap 这样的排序类，LinkedHashMap 最大的特点在于有序，但是它的有序主要体现在先进先出 FIFO 上。没错， LinkedHashMap 主要依靠双向链表和 Hash 表来实现的。（其实就是保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的。不过在遍历的时候会比 HashMap 慢。但是 key 和 value 均允许为空）

使用示例：

public static void main(String[] args) {
    LinkedHashMap<String, Temp> map = new LinkedHashMap<>();
    map.put("张三", new Temp(18, "张三"));
    map.put("张三02", new Temp(18, "张三"));
    map.put("王二", new Temp(14, "王二"));
    map.put("赵六", new Temp(12, "赵六"));
    map.forEach((k, v) -> {
        System.out.printf("key：%s：  value：%s \n", k, v);
    });
}

存储原理，设置了一个 EntryHeader 用来维持链表的顺序

发生 Hash 冲突时如何指向

仔细看下图，这里虽然在计算 hashcode 时还是发生了 hash 冲突，采用链地址法解决了冲突，但是这里的 Entry 对象是采用双向链表保存的，即每个 Entry 都有一个 after 和 before 的属性。所以当插入一个 entry 时，如果发生了冲突，就可以将新的 Entry 插入 Entry 链表中的头部，但是按照双向链表的角度来说，又会将该 Entry 插入到双向链表的尾部。

ConcurrentHashMap

这个 Map 实现类是在 jdk1.5 中加入的，其在 jdk1.6/1.7 中的主要实现原理是 segment 段锁，它不再使用和 HashTable 一样的 synchronize 一样的关键字对整个方法进行加锁，而是转而 利用 segment 段落锁 来对其进行加锁，以保证 Map 的多线程安全。

其实可以理解为，一个 ConcurrentHashMap 是由多个 HashTable 组成，所以它允许获取不用段锁的线程同时持有该资源，segment 有多少个，理论上就可以同时有多少个线程来持有它这个资源。

其默认的 segment 是一个数组，默认长度为 16。也就是说理论商可以提高 16 倍的性能。

TreeMap

TreeMap 不允许 key 的值为 null，且它也是 SortedMap 这个接口的唯一实现类

TreeMap 也是一个很常用的 Map 实现类，因为他具有一个很大的特点就是会对 Key 进行排序，使用了 TreeMap 存储键值对，再使用 Iterator 进行遍历输出时，会发现其默认采用 key 由小到大的顺序输出键值对，如果想要按照其他的方式来排序，需要重写也就是 override 它的 compartor 接口。

使用示例：

public static void main(String[] args) {
    // 这里 -o1.compareTo(o2) 表示倒序
    TreeMap<String, Integer> map = new TreeMap<>((o1, o2) -> -o1.compareTo(o2));

    map.put("key_1", 1);
    map.put("key_2", 2);
    map.put("key_3", 3);

    Set<String> keys = map.keySet();
    for (String key : keys) {
        System.out.println(key + ":" + map.get(key));
    }
}

输出

key_3:3
key_2:2
key_1:1

另外，TreeMap 底层的存储结构也是一颗红黑树。因为红黑树查找效率高，只有 $O(lgn)$ 。它是一种自平衡的二叉查找树。在每次插入和删除节点时，都可以自动调节树结构，以保证树的高度是 $lgn$ 。

WeakHashMap

在 Map 家族中，WeakHashMap 是一个很特殊的成员，从名字上看与 HashMap 相关，但是与 HashMap 有着很大的差别，翻译成中文后表示弱 HashMap，俗称缓存 HashMap。

WeakHashMap 它是一个 “弱键”，它的 Key 值和 Value 都可以是 null，而且其 Map 中如果这个 Key 值指向的对象没被使用，此时触发了 GC，该对象就会被回收掉的。

其原理主要是使用的 WeakReference 和 ReferenceQueue 实现的，其 key 就是 weakReference，而 ReferenceQueue 中保存了被回收的 Key-Value。

如果当其中一个 Key-Value 不再使用被回收时，就将其加入 ReferenceQueue 队列中。当下次再次调用该 WeakHashMap 时，就会去更新该 map，比如 ReferenceQueue 中的 key-value，将其中包含的 key-value 全部删除掉。这就是所谓的 “自动删除”。

具体细节参考：【集合系列】- 深入浅出的分析 WeakHashMap

如何使 Map 线程安全？

我们都知道很多 Map 是非线程安全的（非同步的）。那么怎么才能让这些 Map 变成线程安全的呢？

下面以 HashMap 为例：

synchronizedMap 是一个方法，HashMap 本身非线程安全的，但是当使用 Collections.synchronizedMap(new HashMap()) 进行包装后就返回一个线程安全的 Map。

点进这个 synchronizedMap 方法内部，可以发现它创建了一个 SynchronizedMap 对象

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

来看 SynchronizedMap 的主要方法

public int size() {
    synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
    synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
    synchronized (mutex) {return m.containsKey(key);}
}
public V get(Object key) {
    synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
    synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
    synchronized (mutex) {return m.remove(key);}
}

从源码可以看出，SynchronizedMap 实现线程安全的方法也是比较简单的，所有方法都是先对锁对象 mutex 上锁，然后再直接调用 Map 类型成员变量 m 的相关方法。

这样一来，线程在执行方法时，只有先获得了 mutex 的锁才能对 m 进行操作。因此，跟 Hashtable 一样，在同一个时间点，只能有一个线程对 SynchronizedMap 对象进行操作，虽然保证了线程安全，却导致了性能低下。

它最大的好处就是传入的是一个 Map 接口，而不是具体的实现类，所以像 TreeMap 这种 Map 实现类就可以通过这个方法来生成一个线程安全的 Map

synchronizedMap(Map) 和 ConcurrentHashMap 区别？

ConcurrentHashMap 是 Java 1.5 中 Hashtable 的替代品，是并发包的一部分。使用 ConcurrentHashMap，不仅可以在并发多线程环境中安全地使用它，而且还提供比 Hashtable 和 synchronizedMap 更好的性能。

但是对于没有给出线程安全却需要线程安全的 Map 实现类就可以使用 synchronizedMap(Map) 来创建了

Reference

【集合系列】- 深入浅出的分析 WeakHashMap java中Map有哪些实现类和使用场景

Map 集合接口​

Map 接口中的常用方法​

HashMap​

Hashtable​

LinkedHashMap​

发生 Hash 冲突时如何指向​

ConcurrentHashMap​

TreeMap​

WeakHashMap​

如何使 Map 线程安全？​

Reference​